In compiler optimization, “register allocation” and “instruction scheduling” are well-known processes that are employed for improving machine performance. A compiler transforms a software program's programming language source code into a machine code (also referred to as “generated code”) that is understandable by computer system. During transformation, an intermediate stage is reached when the compiler provides intermediate representation of the internal representation of the transformation process. Optimizing a compiler refers to aiming a compiler to make such transformation in an efficient manner (e.g., producing an efficient code using the least amount of resources).
Register allocation refers to mapping program variables (also referred to as “pseudos”) with central processing unit (CPU) registers (also referred to as “processor registers”) residing at a processor of a computer system. Instruction scheduling is used to increase a processor's instruction throughput. Instruction scheduling refers to rearranging the order of instructions of software program code in a processor pipeline to avoid pipeline stalls without changing the meaning or the goal of the software program code.
A number of processor registers on any processor is considered limited since that number strictly depends on the architectural design of the processor and thus, any number of available processor registers is considered a smaller number compared to the large number of data items or program variables a typical software programs has to process. This discrepancy, known as “high register pressure”, leads to what is typically referred to as “spilling”. Spilling occurs when there are more live programs variables than there are available processor registers and the compiler is forced to spill some of the program variables to memory (from processor registers). Spilling leads to inefficiency because accessing memory is typically slower than accessing registers.
A program variable living at a program point refers to a variable that contains a value that can be used by its software program at the program point or at the subsequently executed program points. Register pressure at a program point is a number of program variables living at the program point of the software program. High register pressure occurs when the number of living program variables is greater than the number of available processor registers.
Although both register allocation and instruction scheduling are used for compiler optimization (which in turn, improves machine performance), the two processes do not always complement each other and, often, act as contradicting optimization processes. For example, instruction scheduling is typically done by removing an instruction from the original instruction list and placing it at the end of a result list without taking into account its overall impact on register allocation, which increases register pressure on subsequent scheduling points. That is, register pressure is considered only at the current scheduling point without taking into account register pressures at other program points (e.g., subsequent scheduling points). A program point is referred to as scheduling point if instruction scheduling is performed at that program point.
Hence, the more frequent the instruction scheduling, the higher the register pressure on subsequent scheduling points or on the holding list of instructions and thus, more spills have to be performed during register allocation, which negatively impacts the process of compiler optimization.